import java.util.Stack;

public class BinaryTree3 {
    public static class Node {
        public Node left;
        public Node right;
        public int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public static void prePrint(Node head) {
        Node stackTop = null;
        Stack<Node> sta = new Stack<>();
        if (head == null) {
            return;
        }
        sta.push(head);
        while (!sta.isEmpty()) {
            stackTop = sta.pop();
            System.out.println(stackTop.value);
            if (stackTop.right != null) {
                sta.push(stackTop.right);
            }
            if (stackTop.left != null) {
                sta.push(stackTop.left);
            }
        }
    }

    public static void midPrint(Node head) {
        Node stackTop = null;
        Stack<Node> sta = new Stack<>();
        if (head == null) {
            return;
        }
        sta.push(head);
        while (!sta.isEmpty()) {
            while (head.left != null) {
                sta.push(head.left);
                head = head.left;
            }
            stackTop = sta.pop();
            System.out.println(stackTop.value);
            if (stackTop.right != null) {
                head = stackTop.right;
                sta.push(head);
            }
        }
    }

    public static void lastPrint(Node head) {
        Node stackTop = null;
        Stack<Node> sta1 = new Stack<>();
        Stack<Node> sta2 = new Stack<>();
        if (head == null) {
            return;
        }
        sta1.push(head);
        while (!sta1.isEmpty()) {
            stackTop = sta1.pop();
            sta2.push(stackTop);
            if (stackTop.left != null) {
                sta1.push(stackTop.left);
            }
            if (stackTop.right != null) {
                sta1.push(stackTop.right);
            }

        }
        while (!sta2.isEmpty()) {
            System.out.println(sta2.pop().value);
        }
    }
}
